package algorithm.arithmetic.二叉树遍历;

/**
 * 给出一棵二叉树的前序和中序遍历，输出后序遍历的结果。
 * 如输入(前序__中序)：ABDHECFG__HDBEAFCG 输出(后序)：HDECFGCA。
 * @author xinchen by 2016/11/25
 * @version 1.0
 */
public class Solution {
    // 给出一棵二叉树的前序和中序遍历，输出后续遍历的结果。
    public static void main(String[] args) {
        String exp = args[0];
        String pre = exp.split("__")[0];
        String post = exp.split("__")[1];
        Node root = new Node();
        root.c = pre.charAt(0);
        for (int i = 1; i < pre.length(); i++) {
            addNode(root, pre.charAt(i), post);
        }
        StringBuilder stringBuilder = new StringBuilder();
        print(root,stringBuilder);
        System.out.println(stringBuilder);
    }

    private static void print(Node node, StringBuilder stringBuilder) {
        if (node.left != null) {
            print(node.left,stringBuilder);
        }
        if (node.right != null) {
            print(node.right,stringBuilder);
        }
        stringBuilder.append(node.c);
    }

    private static void addNode(Node node, char c, String post) {
        int charIndex = post.indexOf(c);
        int index = post.indexOf(node.c);
        if (index > charIndex) {
            if (node.left == null) {
                node.left = new Node();
                node.left.c = c;
            } else {
                addNode(node.left, c, post);
            }
        } else {
            if (node.right == null) {
                node.right = new Node();
                node.right.c = c;
            } else {
                addNode(node.right, c, post);
            }
        }
    }

    private static class Node {
        Node left;
        Node right;
        char c;
    }
}
